package com.leetcode.题库;

/**
 * @author 覃国强
 * @date 2022-03-24 20:02
 */
public class 题库_0138_复制带随机指针的链表 {


  static
  class Solution {
    public Node copyRandomList(Node head) {
      if (head == null) {
        return head;
      }

      Node node = head;
      while (node != null) {
        Node copy = new Node(node.val);
        copy.next = node.next;
        node.next = copy;
        node = copy.next;
      }

      node = head;
      while (node != null) {
        Node copy = node.next;
        if (node.random != null) {
          copy.random = node.random.next;
        }
        node = copy.next;
      }


      node = head;
      Node answerHead = new Node(0);
      Node answerTail = answerHead;
      while (node != null) {
        Node copy = node.next;
        node.next = copy.next;

        answerTail.next = copy;
        answerTail = copy;

        node = copy.next;
      }

      return answerHead.next;
    }
  }

  static
  class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
      this.val = val;
      this.next = null;
      this.random = null;
    }
  }
}
